package com.wenhai.liuyubobobo.imooc.heap;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

/**
 * 最大堆/大根堆
 *
 * @author wenhai
 * @date   2021/3/9
 */
public class MaxHeap<E extends Comparable<E>> {
    private int size;
    private List<E> data;

    public MaxHeap() {
        data = new ArrayList<>();
    }

    public MaxHeap(int capacity) {
        data = new ArrayList<>(capacity);
    }

    public MaxHeap(List<E> data) {
        this.data = data;
    }

    public MaxHeap(E[] data) {
        if (data != null) {
            this.data = new ArrayList<>(data.length);
            this.data.addAll(Arrays.asList(data));
            this.size = this.data.size();
            for (int i = (size >>> 1) - 1; i >= 0; i--){
                siftDown(i);
            }
//            for (int i = parentIndex(data.length - 1); i >= 0; i--) {
//                siftDown(i);
//            }
        }
    }

    public int size() {
        return data.size();
    }

    public boolean isEmpty() {
        return data.isEmpty();
    }

    private int parentIndex(int childIndex) {
        if (childIndex <= 0) {
            throw new IllegalArgumentException("Index must be not less than 0 :" + childIndex);
        }
        return (childIndex - 1) / 2;
    }

    private int leftChildIndex(int parentIndex) {
        if (parentIndex < 0) {
            throw new IllegalArgumentException("Index must be not negative :" + parentIndex);
        }

        return parentIndex * 2 + 1;
    }

    private int rightChildIndex(int parentIndex) {
        if (parentIndex < 0) {
            throw new IllegalArgumentException("Index must be not negative :" + parentIndex);
        }

        return parentIndex * 2 + 2;
    }

    public void add(E e) {
        data.add(e);
        siftUp(data.size() - 1);
    }


    private void siftUp(int index) {
        while (index > 0 && data.get(index).compareTo(data.get(parentIndex(index))) > 0) {
            swap(data, index, parentIndex(index));
            index = parentIndex(index);
        }
    }

    public E peekMax() {
        if (data.size()==0) {
            throw new IllegalStateException("Heap is Empty");
        }
        return data.get(0);
    }


    public E getMax() {
        E res = peekMax();
        swap(data, 0, data.size() - 1);
        data.remove(data.size() - 1);
        siftDown(0);
        return res;

    }

    private void siftDown2(int index) {
        int maxChildIndex = maxChild(index);
        while (maxChildIndex > 0 && data.get(index).compareTo(data.get(maxChildIndex)) < 0) {
            swap(data, index, maxChildIndex);
            index = maxChildIndex;
            maxChildIndex = maxChild(maxChildIndex);
        }
    }

    private int maxChild(int parent) {
        int leftIndex = leftChildIndex(parent);
        int rightIndex = rightChildIndex(parent);
        if (leftIndex < data.size()  && rightIndex < data.size() ) {
            if (data.get(leftIndex).compareTo(data.get(rightIndex)) > 0) {
                return leftIndex;
            }
            return rightIndex;
        }
        if (leftIndex < data.size() && rightIndex > data.size()) {
            return leftIndex;
        }
        if (leftIndex > data.size() && rightIndex < data.size()) {
            return rightIndex;
        }
        return -1;
    }

    private void siftDown(int index) {
        while (leftChildIndex(index) < data.size()) {
            int maxIndex = leftChildIndex(index);
            if (maxIndex + 1 < data.size() && data.get(maxIndex + 1).compareTo(data.get(maxIndex)) > 0) {
                maxIndex++;
            }
            if (data.get(index).compareTo(data.get(maxIndex)) >= 0) {
                break;
            }
            swap(data,index,maxIndex);
            index = maxIndex;
        }
    }

    private void swap(List<E> data, int from, int to) {
        if (from < 0 || to < 0 || from > data.size() || to > data.size()) {
            throw new IndexOutOfBoundsException("Illegal from index or to index ");
        }
        E temp = data.get(from);
        data.set(from, data.get(to));
        data.set(to, temp);
    }


    public E replace(E e) {
        E max = peekMax();
        data.set(0, e);
        siftDown(0);
        return max;
    }

    @Override
    public String toString() {
        return "MaxHeap{" +
                "size=" + size +
                ", data=" + data +
                '}';
    }

    public static void main(String[] args) {
        int n = 1000000;
        Integer[] arr = new Integer[n];
        Random random = new Random();
        for (int i = 0; i < n; i++) {
            arr[i] = (random.nextInt(Integer.MAX_VALUE));
        }
        Integer[] arr2 = Arrays.copyOf(arr, arr.length);
        System.out.println("非 Heapity 耗时：" + testHeap(arr, false));
        System.out.println("Heapity 耗时：" + testHeap(arr2, true));
    }

    private static double testHeap(Integer[] testData, boolean isHeapify) {
        long startTime  = System.nanoTime();
        MaxHeap<Integer> heap;
        if (isHeapify) {
            heap = new MaxHeap<>(testData);
        }else {
            heap = new MaxHeap<>(testData.length);
            for (Integer data : testData) {
                heap.add(data);
            }
        }
        int[] arr = new int[testData.length];
        for (int i = 0; i < testData.length; i++) {
            arr[i] = heap.getMax();
        }
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > arr[i - 1]) {
                throw new RuntimeException("算法错误");
            }
        }
        long endTime = System.nanoTime();

        return (endTime-startTime)/1000000000.0;
    }
}
